import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

public class BinaryHeap<E> extends ArrayList<E>
{
	// min-heap

	private Comparator<E> comparator;
	private Map<E, Integer> indices;

	public BinaryHeap(Comparator<E> comparator)
	{
		super();
		this.comparator = comparator;
		this.indices = new HashMap<E, Integer>();
	}

	public void addHeap(E arg0)
	{
		add(arg0); // step 1
		int index = size() - 1;
		indices.put(arg0, index);
		while (index > 0 && comparator.compare(get((index - 1) / 2), arg0) > 0)
		{ // step 2
			swap(index, (index - 1) / 2); // step 3
			index = (index - 1) / 2;
		}
	}

	// preferably use swap for convenient indexed array handling
	public E popRoot()
	{
		int size = size();
		E root = get(0); // step 1
		indices.remove(root);
		if (size == 1)
		{
			remove(0);
		} else
		{
			set(0, remove(size - 1));
			E newRoot = get(0);
			indices.put(newRoot, 0); // get(0) has changed due to above
			size--;
			int index = 0;

			while (index * 2 + 1 < size)
			{
				// find smallest child
				int smallerChildIndex;
				E smallerChild;
				if (index * 2 + 2 < size) //there exists a second child
				{
					E first = get(index * 2 + 1), second = get(index * 2 + 2);
					if (comparator.compare(first, second) < 0)
					{
						smallerChild = first;
						smallerChildIndex = index * 2 + 1;
					} else
					{
						smallerChild = second;
						smallerChildIndex = index * 2 + 2;
					}
				} else
				{
					smallerChildIndex = index * 2 + 1;
					smallerChild = get(smallerChildIndex);
				}

				if (comparator.compare(newRoot, smallerChild) > 0) // step 3
				{
					swap(index, smallerChildIndex);
					index = smallerChildIndex;
					continue;
				} else
				{ // step 2
					break; // satisfied both requirements
				}
			}
		}
		return root;
	}

	public void update(E arg0)
	{
		int index = indices.get(arg0);
		while (index > 0 && comparator.compare(get((index - 1) / 2), arg0) > 0)
		{ // step 2
			swap(index, (index - 1) / 2); // step 3
			index = (index - 1) / 2;
		}
	}

	public E find(E arg0)
	{
		Integer index = indices.get(arg0);
		return index != null ? get(index) : null;
	}

	private void swap(int a, int b)
	{
		indices.put(get(a), b);
		indices.put(get(b), a);
		set(b, set(a, get(b)));
	}

	@Override
	public String toString()
	{
		String temp = "";
		for (E node : this)
			temp += ((SearchNode) node).f() + " ";
		return temp + "\n";
	}

}
